﻿#define _CRT_SECURE_NO_WARNINGS
// ↑ 将本行在代码放在第一行可以避免 scanf的报错问题（仅在VS编译器里）
//【初阶】47.堆


//【头文件包含】

#include"Heap.h"


//【结构体声明】
/*定义一种链式树结构*/typedef struct TreeNode
{
	int val;
	struct TreeNode* leftChild;
	struct TreeNode* rightBrother;
};

//【函数声明】
void Test1();

//【主函数】
int main()
{

	Test1();
	return 0;
}

//【函数】

/*测试用例*/void Test1()
{
	int arr[] = { 27,15,19,18,28,34,65,49,25,37 };

	int sz = sizeof(arr) / sizeof(arr[0]);
	Hp  heap1;
	HeapInit(&heap1, arr, sz);
	HeapPrint(&heap1);

	HeapPush(&heap1, 13);
	HeapPush(&heap1, 14);
	HeapPush(&heap1, 15);

	HeapPrint(&heap1);
	HeapPop(&heap1);
	HeapPrint(&heap1);

	HeapSort(heap1.a,heap1.size);
	HeapPrint(&heap1);
	printf("size = %d high = %d\n", heap1.size , HeapHigh(&heap1));
	HeapPrint2(&heap1);


}

/*复习向下调整算法*/void myadjust_S(HpDataType* arr, int sz, int root)
{
	int parent = root;
	int child = root * 2 + 1;
	while (child < sz)
	{
		if ((child + 1) < sz && arr[child + 1] < arr[child])
		{
			child = child + 1;
		}

		if (arr[parent] > arr[child])
		{
			Swap(&arr[parent], &arr[child]);
		}
		else
		{
			break;
		}
		parent = child;
		child = parent * 2 + 1;
	}
}


//【笔记】
//【初阶】47.堆
// 堆的结构更适合用数组来存
// 父节点下标i  左子节点 i*2+1  右子节点i*2+2
// 子节点下标i  父节点下标(i-1)/2
// 数组建堆主要依赖向下调整算法，调整的树左右子树都是对应形式的堆
// 堆的快排实现：利用小堆排降序，利用大堆排升序；
// 堆的插入：创建一个向上调整的算法， 通过尾插，然后将插入值调整到合适位置
// 堆的删除：是删除堆顶的数据，将要删的堆顶数据和堆尾数据交换，在进行一次向下调整即可

